/*
 * @lc app=leetcode.cn id=399 lang=cpp
 * @lcpr version=30204
 *
 * [399] 除法求值
 */


// @lcpr-template-start
using namespace std;
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
// @lcpr-template-end
// @lc code=start
class Solution {
public:
    // 并查集节点结构：记录父节点和到父节点的权重（当前节点 / 父节点）
    struct Node {
        string parent;
        double weight;
        // 1. 默认构造函数（无参，给成员变量赋默认值）
        Node() : parent(""), weight(1.0) {}  
        Node(string p, double w) : parent(p), weight(w) {}
    };

    // 查找根节点，并更新路径上的权重（路径压缩）
    pair<string, double> find(unordered_map<string, Node>& nodes, string x) {
        if (nodes.find(x) == nodes.end()) {
            return {"", 0.0}; // 节点不存在
        }
        if (nodes[x].parent != x) {
            // 递归查找根节点，并更新当前节点的父节点为根节点，权重累乘
            auto [root, w] = find(nodes, nodes[x].parent);
            nodes[x].parent = root;
            nodes[x].weight *= w;
        }
        return {nodes[x].parent, nodes[x].weight};
    }
    vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
        unordered_map<string, Node> nodes;

        // 初始化并查集，建立变量间的关系
        for (int i = 0; i < equations.size(); ++i) {
            string a = equations[i][0];
            string b = equations[i][1];
            double val = values[i];

            // 若节点不存在，则初始化（父节点为自身，权重为1.0）
            if (nodes.find(a) == nodes.end()) {
                nodes[a] = Node(a, 1.0);
            }
            if (nodes.find(b) == nodes.end()) {
                nodes[b] = Node(b, 1.0);
            }

            // 查找a和b的根节点
            auto [rootA, weightA] = find(nodes, a);
            auto [rootB, weightB] = find(nodes, b);

            // 若根节点不同，则合并（让rootB的父节点指向rootA）
            if (rootA != rootB) {
                nodes[rootB].parent = rootA;
                // 权重关系：a/b = val => (rootA * weightA) / (rootB * weightB) = val => rootB = rootA * weightA / (val * weightB)
                nodes[rootB].weight = weightA / (val * weightB);
            }
        }

        // 处理查询
        vector<double> res;
        for (auto& q : queries) {
            string c = q[0];
            string d = q[1];

            // 若任一节点不存在，结果为-1.0
            if (nodes.find(c) == nodes.end() || nodes.find(d) == nodes.end()) {
                res.push_back(-1.0);
                continue;
            }

            // 查找根节点
            auto [rootC, weightC] = find(nodes, c);
            auto [rootD, weightD] = find(nodes, d);

            // 根节点不同，无法计算，结果为-1.0
            if (rootC != rootD) {
                res.push_back(-1.0);
            } 
            else {
                // 计算结果：c/d = (rootC * weightC) / (rootD * weightD) = weightC / weightD（因rootC=rootD）
                res.push_back(weightC / weightD);
            }
        }

        return res;
    }
};
// @lc code=end



/*
// @lcpr case=start
// [["a","b"],["b","c"]]\n[2.0,3.0]\n[["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]\n
// @lcpr case=end

// @lcpr case=start
// [["a","b"],["b","c"],["bc","cd"]]\n[1.5,2.5,5.0]\n[["a","c"],["c","b"],["bc","cd"],["cd","bc"]]\n
// @lcpr case=end

// @lcpr case=start
// [["a","b"]]\n[0.5]\n[["a","b"],["b","a"],["a","c"],["x","y"]]\n
// @lcpr case=end

 */

